package com.dhu.graph.basic.GraphImpls;

import com.dhu.graph.basic.AbstractGraph;
import com.dhu.graph.basic.edge.Edge;
import com.dhu.graph.utils.Bag;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-03
 * @ Description：有向图
 * @ Modified By：
 * @ Version:
 */
public class DiGraph implements AbstractGraph {
    private final int V;    // 顶点数
    private int E;  // 边数
    private Bag<Integer>[] adj;

    public DiGraph(int v) {
        this.V = v;
        this.adj = (Bag<Integer>[]) new Bag[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new Bag<Integer>();
        }
    }
    @Override
    public int V() {
        return this.V;
    }
    @Override
    public int E() {
        return this.E;
    }
    @Override
    public Iterable<Integer> adj(int v) {
        return this.adj[v];
    }

    /**
     * 添加由v指向w的有向边
     *
     * @param v
     * @param w
     */
    @Override
    public void addEdge(int v, int w) {
        adj[v].put(w);
        E++;
    }

    @Override
    public void addEdge(Edge e) {
        throw new RuntimeException("This method only can be call in Weight Graph,cause int this Graph edge combined with tow ints");
    }

    /**
     * @return 该图的反向图
     */
    public DiGraph reserve() {
        DiGraph diGraph = new DiGraph(this.V);
        for (int i = 0; i < V; i++) {
            for (Integer w : adj[i]) {
                diGraph.addEdge(w, i);
            }
        }
        return diGraph;
    }

}
